package com.nlp.trie.unigramSeg;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 一元分词
 * @author ygsong.abcft
 *
 */
public class Segmenter {

	final static double minValue = -1000000.0;
	private static final SuffixTrie dic = SuffixTrie.getInstance();
	String text;
	int[] prevNode;
	public Segmenter(String t) {
		text = t;
	}
	
	public List<String> split(){
		prevNode = new int[text.length()+1];//最佳前驱节点数组
		double[] prob = new double[text.length()+1];//节点概率
		prevNode[0] = 0;
		
		//用来存放前驱词的集合
		ArrayList<WordEntry> prevWords = new ArrayList<>();
		//求出每个节点的最佳前驱节点
		for (int i = 1; i < prevNode.length; i++) {
			double maxProb = minValue;//候选节点概率
			//System.out.println("minValue "+minValue);
			int maxNode = 0;//候选最佳前驱节点
			
			//从词典中查找前驱词的集合
			dic.matchAll(text, i-1, prevWords);
			
			//根据
			for (WordEntry word : prevWords) {
				double wordProb = Math.log(word.freq) - Math.log(dic.wordCount);
				System.out.println("wordProb "+wordProb);
				int start = i - word.word.length();//候选前驱节点
				double nodeProb = prob[start] + wordProb;//候选节点概率
				if (nodeProb > maxProb) {//概率最大的算作最佳前驱
					maxNode = start;
					maxProb = nodeProb;
				}
			}
			prob[i] = maxProb;//节点概率
			prevNode[i] = maxNode;//最佳前驱节点;
		}
		return bestPath();
	}

	/**
	 * 根据最佳前驱节点数组回溯求解词序列
	 * @return
	 */
	private List<String> bestPath() {
		//最佳节点序列
		Deque<Integer> path = new ArrayDeque<>();
		//从后向前回溯最佳前驱节点
		for (int i = text.length(); i > 0; i = prevNode[i]) {
			path.push(i);
		}
		//切分出来的词序列
		List<String> words = new ArrayList<>();
		int start = 0;
		for (Integer end : path) {
			words.add(text.substring(start, end));
			start = end;
		}
		return words;
	}
	
	public static void main(String[] args) {
		String sentence = "阿里巴巴";
		Segmenter seg = new Segmenter(sentence);
		List<String> ret = seg.split();
		for (String string : ret) {
			System.out.println(string);
		}
	}
}
